Recently, an encoding method using LDPC codes has attracted lots of attention. In 1962, Gallager has suggested LDPC codes as low-density linear block codes since most elements of a parity check matrix H are zero. LDPC codes were forgotten since the LDPC codes are very complicated so that they could not be realized with technologies of that time. In 1995, LDPC codes were recognized again and excellent performance thereof was validated. Recently, intensive studies have been done on LDPC codes (see: [1] Robert G. Gallager, “Low-Density Parity-Check Codes”, The MIT Press, Sep. 15, 1963, and [2] D. J. C. Mackay, Good error-correcting codes based on very sparse matrices, IEEE Trans. Inform. Theory, IT-45, pp. 399-431 (1999)).
Since the number of 1s in a parity check matrix of an LDPC code is very small, the parity check matrix allows decoding even for a very large block size through iterative decoding. Thus, as the block size increases, the performance of the parity check matrix of an LDPC code approaches Shannon's channel capacity limit as that of a turbo code. The number of 1s included in a row or column of the parity check matrix is referred to as a weight.
An LDPC code can be described using an (n−k)×n parity check matrix H. A generator matrix G corresponding to the parity check matrix H can be obtained by Equation 1.H·G=0  [Equation 1]
In an encoding and decoding method using LDPC codes, the transmitting side can encode input data according to Equation 2 using the generator matrix G that has the relationship of Equation 1 with the parity check matrix.c=G·x,  [Equation 2]
where “c” denotes a codeword and “x” denotes information bits.
A description will now be given of a conventional decoding method using the H matrix.
A decoder at the receiving side must obtain information bits x from a codeword c that is an encoding result at the transmitting side. The decoder determines the information bits x using a condition “Hc=0”. Specifically, when a codeword c′ is received, the value of Hc′ is calculated. If the value of Hc′ is 0, it is determined that first k bits of the codeword c′ are decoded information bits. If the value of Hc′ is not 0, the information bits x are reconstructed by finding a codeword c′, which satisfies a check equation “Hc′=0”, using a graph-based sum-product algorithm, a belief propagation algorithm, or the like. The check equation “Hc′=0” can be changed to “c′HT=0” according to the information bits and the G matrix. Thus, the check equation can be changed according to the relationship between the information bits and the G matrix.
FIG. 1 illustrates a bipartite graph that expresses a parity check matrix H. In FIG. 1, “CNU” stands for a check node unit and “VNU” stands for a variable (or bit) node unit. A decoding procedure that is performed by applying an algorithm to the bipartite graph can be divided into the following three main processes.
1. Check-to-variable node likelihood value update.
2. Variable-to-check node likelihood value update.
3. Determination of decoded value based on variable (or bit) node likelihood.
Likelihood values received over a channel are input at an initialization step, and then the first process is performed to update the check nodes. After the first process is completed, the second process is carried out to perform the variable-to-check node likelihood value update. After the first and second processes are completed, a decoded value is determined using the likelihood values received over the channel and the likelihood values updated through the first and second processes.
In the decoding procedure, if the determined decoded value c′ satisfies a check equation “Hc′=0” at the third process after the first and second processes are completed, the value c′ is determined to be a correctly received decoded value, otherwise, the first and second processes are iterated up to a specific number of times until the check equation is satisfied. The likelihood value update processes of the first and second processes are iterated the same number of times as the number of nonzero elements (i.e., the number of 1s) included in each row or column of the parity check matrix. That is, the check-to-variable update of the first process and the variable-to-check update of the second process are performed on positions of the parity check matrix H that correspond to weights thereof. As the first and second processes are iterated, the reliability of the likelihood values of the check and variable nodes increases, thereby approaching a true value of the codeword to be obtained.
Recent LDPC encoding methods generally encode data using the parity check matrix H rather than the generator matrix G. Thus, as described above, the parity check matrix H can be considered the most important element of the encoding method using LDPC codes. Since the parity check matrix H has a size of about 1000×2000 or more, it requires a number of calculations in the encoding and decoding processes, complicates the implementation, and requires a large storage space.